package com.leetcode.dynamic;

/**
 * @program: leetcode  1769
 * @author: jzhou
 * @date: 2022-12-02 18:48
 * @version: 1.0
 * @description: 移动所有球到每个盒子所需的最小操作数
 *      把所有球转移到当前下标为 i+1 的盒子的操作数 可以由 operation + left - right 快速求出
 *      因为原来左侧的 left 个球各需要多操作一步 原来右侧的 right 个球可以各少操作一步
 **/
public class MinOperations {

    public int[] minOperations(String boxes) {

        int length = boxes.length();
        int left = boxes.charAt(0) - '0',right = 0, op = 0;
        for (int i = 1; i < length; i++) {
            if (boxes.charAt(i) == '1'){
                right++;
                op += i;
            }
        }
        int[] arr = new int[length];
        arr[0] = op;
        for (int i = 1; i < length; i++) {
            arr[i] = arr[i-1] + left -right;
            if (boxes.charAt(i) == '1'){
                right--;
                left++;
            }
        }
        return arr;
    }
}
